package com.atguigu.heap;

import java.util.Arrays;

public class HeapSort<E extends Comparable<E>> {

    private HeapSort(){}

    public static <E extends Comparable<E>> void Sort(E[]data){
        MaxHeap<E>heap=new MaxHeap<>();
        for(E e:data){
            heap.add(e);
        }
        for(int i=data.length-1;i>=0;i--){
            data[i]=heap.extractMax();
        }
    }
    public static <E extends Comparable<E>> void Sort2(E[]data){
        /*int size=data.length-1;
        heapify(data,size);
        while(size>0){
            swap(data,0,size);
            size--;
            siftDown(data,0,size);
        }*/
        if(data.length<=1) return;
        for(int i=(data.length-2)/2;i>=0;i--){
            siftDown(data,i,data.length);
        }
        for (int i = data.length-1; i >=0; i--) {
            swap(data,0,i);
            siftDown(data,0,i);
        }
    }
    //元素下沉操作
    private static <E extends Comparable<E>> void siftDown(E[]data,int k,int size) {
        while(leftChild(k)<size){
            int j=leftChild(k);
            if(j+1<size&&data[j+1].compareTo(data[j])>0){
                j=j+1;
            }
            //data[j]是leftChild和rightChild中的最大值
            if(data[k].compareTo(data[j])>=0){
                break;
            }
            swap(data,k,j);
            k=j;
        }
    }
    private static <E extends Comparable<E>> void swap(E[] data, int k, int j){
        E temp=data[k];
        data[k]=data[j];
        data[j]=temp;
    }
    //上浮操作
    private static <E extends Comparable<E>> void siftUp(E[]data,int k) {
        while(k>0&&data[parent(k)].compareTo(data[k])<0){
            swap(data,parent(k),k);
            k=parent(k);
        }
    }
    //返回完全二叉树的数组表示，一个索引所表示的元素的父亲节点的索引
    private static <E extends Comparable<E>> int parent(int index){
        if(index==0){
            throw new IllegalArgumentException("index-0 doesn't have parent");
        }
        return (index-1)/2;
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private static <E extends Comparable<E>> int leftChild(int index){
        return index*2+1;
    }
    //返回完全二叉树的数组表示中，一个索引所表示的元素的右 孩子节点的索引
    private static <E extends Comparable<E>> int rightChild(int index){
        return index*2+2;
    }

}
